// compile: g++ -o single_linkedlist single_linkedlist.cc -std=c++11
#include "single_linkedlist.h"

#include <iostream>
using namespace std;
SingleLinkedList::SingleLinkedList() { dummy_ = new ListNode(-1); }
SingleLinkedList::~SingleLinkedList() {
  ListNode* head = dummy_->next_;
  while (head) {
    dummy_->next_ = head->next_;
    delete head;
    head = dummy_->next_;
  }
  delete dummy_;
  dummy_ = nullptr;
}
void SingleLinkedList::Show() {
  ListNode* cur = dummy_->next_;
  while (cur) {
    cout << cur->val_ << " ";
    cur = cur->next_;
  }
  cout << endl;
}
void SingleLinkedList::InsertBegin(int val) {
  ListNode* node = new ListNode(val);
  node->next_ = dummy_->next_;
  dummy_->next_ = node;
}
//
void SingleLinkedList::InsertEnd(int val) {
  ListNode* p = dummy_;
  while (p->next_) p = p->next_;       // O(n)的搜索操作
  ListNode* node = new ListNode(val);  // O(1)的增加操作
  node->next_ = p->next_;
  p->next_ = node;
}
// 插入一个值为val的节点到 第idx节点后（idx从1开始）
void SingleLinkedList::InsertAfter(int idx, int val) {
  ListNode* p = dummy_;
  while (idx--) {
    p = p->next_;
    if (!p) {
      cerr << "idx值错误" << endl;
      return;
    }
  }
  ListNode* node = new ListNode(val);
  node->next_ = p->next_;
  p->next_ = node;
}
void SingleLinkedList::DeleteAny(int val) {
  ListNode* pre = dummy_;
  ListNode* cur = dummy_->next_;
  while (cur) {
    if (val == cur->val_) {
      pre->next_ = cur->next_;
      delete cur;
      return;
    } else {
      pre = cur;
      cur = cur->next_;
    }
  }
  return;
}
void SingleLinkedList::DeleteAll(int val) {
  ListNode* pre = dummy_;
  ListNode* cur = dummy_->next_;
  while (cur) {
    if (val == cur->val_) {
      pre->next_ = cur->next_;
      delete cur;
      cur = pre->next_;
    } else {
      pre = cur;
      cur = cur->next_;
    }
  }
  return;
}
// 返回一个int， 表示链表中的第一个val值是第几个节点（从1开始），如果没有返回-1
int SingleLinkedList::Find(int val) {
  int ans = 1;
  ListNode* cur = dummy_->next_;
  while (cur) {
    if (cur->val_ == val) {
      return ans;
    } else {
      cur = cur->next_;
      ++ans;
    }
  }
  return -1;
}

int main() {
  SingleLinkedList sl;
  sl.InsertBegin(0);
  sl.InsertEnd(2);
  sl.InsertAfter(1, 1);
  cout << sl.Find(1) << endl;
  sl.InsertAfter(2, 4);
  sl.InsertBegin(4);
  sl.InsertEnd(4);
  sl.Show();
  sl.DeleteAny(4);
  sl.Show();
  sl.DeleteAll(4);
  sl.Show();
}